class Solution {
public:
/*** 时间复杂度超O(n)
  // 异或
    int singleNonDuplicate(vector<int>& nums) {
        int ret = nums[0];
        for(int i = 1;i < nums.size(); ++i)
            ret ^= nums[i];
        return ret;
    }
***/

  /*由于只出现一次的元素所在下标 x 的左边有偶数个元素，因此下标 x 一定是偶数。二分查找的目标是找到满足 nums[x] != nums[x+1] 的最小的偶数下标 x，则下标x处的元素是只出现一次的元素。
初始时，二分查找的左边界是 0，右边界是数组的最大偶数下标，由于数组的长度是奇数，因此数组的最大偶数下标等于数组的长度减 1。每次取左右边界的平均值mid 作为待判断的下标，如果 mid 是奇数则将 mid 减 1，确保 mid 是偶数，比较 nums[mid] 和 nums[mid+1] 是否相等，如果相等则 mid<x，调整左边界，否则mid≥x，调整右边界。调整边界之后继续二分查找，直到确定下标 x 的值。
得到下标 x 的值之后，nums[x] 即为只出现一次的元素 **/
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size()-1;
        while(left < right){
            int mid = left+(right-left)/2;
            mid -= mid & 1; // 确保mid为偶数
            if(nums[mid+1] == nums[mid])
                left = mid + 2;  
            else right = mid;
        }
        return nums[left];
    }
};